// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。

// 思路1， 暴力解法 + 优化
function largestRectangleArea(heights) {
    heights.unshift(0)  //递增或者递减情况下的问题
    heights.push(0)
    // 记录heights[i]左边比它小的第一个索引位置
    let minLeftIndex = new Array(heights.length)
    minLeftIndex[0] = -1
    // 记录heights[i]右边比它小的第一个索引位置
    let minRightIndex = new Array(heights.length)
    minRightIndex[heights.length - 1] = heights.length
    // [-1,0,0,2,3,2,5,0]
    for (let i = 1; i < heights.length; i++) {
        let left = i - 1
        while (left > 0 && heights[left] >= heights[i]) {
            left = minLeftIndex[left]
        }
        minLeftIndex[i] = left
    }
    // [8,2,7,5,5,7,7,8]
    for (let i = heights.length - 2; i >= 0; i--) {
        let right = i + 1
        while (right < heights.length && heights[right] >= heights[i]) {
            right = minRightIndex[right]
        }
        minRightIndex[i] = right
    }
    let maxArea = 0
    for (let i = 0; i < heights.length; i++) {
        let area = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1)
        maxArea = Math.max(area, maxArea)        
    }
    return maxArea
}

let heights = [2,1,5,6,2,3]
console.log(largestRectangleArea(heights))

// 思路2，单调栈
// 接雨水是单调递减栈，找的是第一个大于栈顶的柱子
// 该题是单调递增栈，找的是第一个小于栈顶的柱子
function largestRectangleArea2(heights) {
    let stack = [0]
    heights.unshift(0)  //递增或者递减情况下的问题
    heights.push(0)
    let result = 0
    for (let i = 0; i < heights.length; i++) {
        while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
            let mid = stack.pop()
            let w = i - stack[stack.length - 1] - 1
            let h = heights[mid]
            result = Math.max(result, w * h)
        }   
        stack.push(i)     
    }
    return result
}

console.log(largestRectangleArea2(heights))